The present invention relates to test pattern generators used in circuit testing and, more particularly, to modified n-bit linear feedback shift register (LFSR) circuit designs.
Traditionally, large scale integrated circuits have needed to be tested for defects or flaws. When only a fraction of the total components produced by a manufacturing process are "good" (i.e., meet the requirements of specifications), something must separate the "good" components from components which contain defects or flaws. Testing does this by applying input stimulus (input test patterns) to the device-under-test and comparing the outputs of the device-under-test with the expected "good" results.
In the past, test pattern generation has been done by hand or with a limited amount of aid from a computer. As the designs of the circuits being tested become increasingly complex, the test time required to generate test patterns by hand increases significantly. For sequential circuitry, the time required has grown at a rate proportional to the number of gates cubed. In reality, costs of manual test pattern generation have not increased at this rate. Rather than invest the time and money required to obtain test results with complete fault coverage, designers often take short cuts which result in inadequate and low-quality test sets.
At the present time the cost of testing depends a great deal on the capital expenditures required for automatic test equipment (ATE). Further, as the number of component input and output pins in the tested circuits increases, and as the components operate at higher frequencies, the complexity and cost of ATE increases. Furthermore, as the complexity of the components increase, so does the number of test patterns. This increase in the number of test patterns results in an increase in test time which then relates to a requirement for additional ATE capacity. Today, a single integrated circuit tester can cost in excess of two million dollars. The price of an hour of testing time can be considerable given the depreciation costs of a circuit tester, tester maintenance costs, and the cost of test engineering support.
An alternative to multi-million-dollar chip testing exists. Designers can incorporate a number of simple design techniques into their circuit design which will reduce the cost of test pattern generation and application while actually allowing better test quality. In addition, it is possible to build into the circuit to be tested a number of capabilities typically required of external test equipment. These built-in self-test (BIST) techniques can greatly simplify automatic test equipment requirements and can result in significant costs savings.
Although testability-improvement techniques and built-in self-test techniques are attractive from the perspective of test cost reduction, they carry with them some significant costs which must be evaluated. Most design-for-test techniques consume chip real estate, power, I/O pins and may impact the speed performance of the circuit during normal operation.
Designs which use built-in self-test provide for generation of input stimulus and evaluation of the circuit response within the actual circuit design. To minimize the on-chip circuitry, external sequencing of the self-test operation is often used. A variety of methods exist for both providing the input stimulus and evaluating the circuit response. Among the most widely used self-test techniques are parallel built-in self-tests of ROMs/RAMs and pseudo-random self-tests.
The addition of a counter to an existing circuit design would enable most built-in self-test techniques to generate test patterns. However, a relatively high number of gates are required to form a counter and a counter does not generate patterns in a pseudo-random fashion. Consequently, many built-in self-test techniques use linear feedback shift registers (LFSR). A LFSR can provide the same test patterns as a counter but can be implemented with a smaller number of gates than a counter of the same number of bits. As a result, the impact on the chip is minimized. In addition, modified versions of the LFSR can be used for both test pattern generation and for compaction of the test results.
The output of an n-bit linear feedback shift register is a pattern of 0's and 1's which is n-bits long. In this case, a bit is an abbreviation for an element of memory which can represent a single binary digit such as a "1" or a "0", and n is in reference to the variability of the length of the register (i.e. number of bits). Thus, the number of possible patterns or states for an n-bit linear feedback shift register is 2.sup.n. If we start the linear feedback shift register in one of these states, it then progresses through some sequence of these states. It can be shown that a periodic succession of states will ultimately result. The feedback function F(X.sub.1, X.sub.2, . . . X.sub.n) can be expressed in the form: EQU F(X.sub.1, X.sub.2, . . . ,X.sub.n)=C.sub.1 X.sub.1 .sym.C.sub.2 X.sub.2 .sym.. . . .sym.C.sub.n X.sub.n
If for each of the constants C, C is either a "0" or a "1", and if the symbol .sym. denotes the exclusive-or (XOR) or the addition module 2 function (wherein the result is "1" for the odd sums and "0" for even sums), then the shift register is called linear. A characteristic of linear feedback is that the value of any of the signals used in the feedback network will have an equal weight in determining the feedback value. Therefore, the resulting test sequence will be psuedo-random in nature. By properly choosing the linear feedback network, the state sequence of an n-bit LFSR can be maximized to a length of 2.sup.n -1 different states. Even with a maximum-length LFSR one state of the LFSR is not included in the sequence. This missing state is often called the "stuck-state" because if the LFSR is initialized to this state, it remains stuck and does not transition to any other state. The inability of an LFSR to generate the entire sequence of 2.sup.n different states (input test patterns) can be an undesirable feature in some testing situations.
Current designs which solve the problem of generating the entire set of input test patterns exist. However, they require the modification of the registers by adding XOR gates between bit-slices. This solution entails building complex, non-standard and expensive registers, which are undesirable if a standard register design exists in a cell library.
The present invention overcomes the problem of generating an incomplete set of input test patterns (e.g., 2.sup.n -1 test patterns) for testing a chip or circuit. Through the present invention, a complete set of input test patterns (i.e., 2.sup.n test patterns) is generated, and this is accomplished in a manner which minimizes the necessary modifications to the integrated circuit design and in a manner which minimizes the number of gates that must be added to the integrated circuit design.
In the present invention, modifying circuitry is added to the feedback network connected to a standard register rather than modifying the standard register itself. Therefore, the modifications made to the test pattern generator do not impact the basic register design. A maximum-length test pattern generator using the present invention includes n memory devices such as an n-bit register, a feedback network and modifying circuitry to allow for 2.sup.n test patterns to be generated.